Data represented in a tree structure is used in a diversity of information processing fields. One of typical examples is a tree structure representation of search information of moving image contents.
FIG. 26 illustrates an example of search information having a tree structure of the moving image contents.
One single moving image content is composed of one or a plurality of scenes, and one scene is composed of one or a plurality of shots. Each shot is provided with data that represents features of the shot, such as motion intensity, frequency of occurrence of color, and a summary of the content of the shot. A tree structure of FIG. 26 represents the search information of the moving image content.
FIG. 26 illustrates the search information of the moving image content. The moving image content of FIG. 26 is composed of three scenes (#0, #1, and #2). Each scene is composed of three shots (#0, #1, and #2). Each shot is provided with data representing motion intensity. In this example, the motion intensity can take three levels of high=3, intermediate=2, and low=1.
The moving image content is a root of the tree structure. Tag information of the motion intensity representing the scene, the shot, and type of data corresponds to a node, and actual data of the motion intensity corresponds to a leaf. The scene is a first branch position if viewed from the root, namely, a node of a first layer, and the shot is a node of a second layer. FIG. 26 illustrates an example only, and the moving image content and its search information typically have a more complex layered structure.
When the search information of the moving image content is handled, requests to retrieve the search data at each leaf for transmission or storage are issued at any time. In this case, since individual retrieved data itself cannot be identified, identification information is attached to the data. For example, as shown in FIG. 26, data 2601 itself is a mere value “1”, and can be used as the search data only when identification information indicating what shot number of what scene number the search data has is attached.
According to MPEG-7, as International Standards of multi-media contents description, relating to the search information such as the moving image content, identification information of search data=leaf is provided by information of a path of the tree extending from the root to the leaf of the tree structure. The path information is referred to as “Tree Branch Code” in MPEG-7. For example, data 2601 of FIG. 26 is uniquely identified by /scene #0/shot #0/motion intensity. Similarly, data 2602 is identified by /scene #0/shot #1/motion intensity, and data 2604 is identified by /scene #1/shot #0/motion intensity. The node is also similarly represented. Identification information of each node is represented by information of a path of the tree from the root to the node of the tree structure.
The information of “scene”, “shot”, and “motion intensity” of the above-mentioned identification information represents an element type of the search information. Numerical information, such as “0” and “1”, is an identification number to identify one element from another when the one element is branched off from one node. Since the numerical information determines the position of each leaf and node in the tree structure, the numerical information is referred to as “position information.” In MPEG-7, the element type information and the position information are separately encoded, and handled together with the search data.
The identification information of each of data 2601-2609 is identical in element type information but different in position information. MPEG-7 defines a data format that allows a plurality of pieces of search data tagged with identification information different only in position information to be transferred or stored together. Therefore, MPEG-7 specifies the following position information encoding/decoding technique for differential encoding a plurality of different pieces of position information.
FIG. 27 is a functional block diagram illustrating the schematic structure of a position information encoding device that performs an MPEG-7 differential encoding process in accordance with a known technique. FIG. 28 illustrates an example of position information to be encoded by an encoding device, and a position information code string encoded by the encoding device in accordance with the known technique, more specifically, illustrates the relationship between the information extracted from the identification information of motion intensity data 2601-2609 of FIG. 26 and the position information code string obtained as a result of encoding.
Leaf 2601 and leaf 2602 as two adjacent pieces of search data of FIG. 26 are compared over a tree path extending from a root 2610 to each of leaves 2601 and 2602. The path from the root (moving image content) to a node (scene #0) at a first layer is common to the two leaves 2601 and 2602. The paths branch off from the scene #0, namely, a node (shot #0 and shot #1) at a second layer. The layer immediately below the branching is referred to as a “branch layer” to the two adjacent leaves. The branch layer of the leaf 2601 and the leaf 2602 is the second layer, namely, a shot layer. Similarly, paths of two adjacent leaves 2603 and 2604 commonly share only the root (moving image content), and already branch off at the nodes at the first layer (scene #0 and scene #1). The branch layer of the two adjacent leaves 2603 and 2604 is the first layer, namely, the scene layer.
The branch layer is now viewed in terms of mutual relationship of the position information extracted from the identification information of FIG. 28. If the values of two adjacent pieces of position information at each layer are compared successively from an upper layer to a lower layer, the branch layer is a layer where the values change first. The known differential encoding technique is based on the premise that the value of the position information increases by 1 at each time, and a change in the value of the position information is converted into information that indicates what layer the position information has changed in value at. The information of the branch layer is thus encoded and the original position information is encoded. It is sufficient in such a differential encoding technique if the number of existing branch layers can be discriminated in the encoding. Information in the differential encoding technique is thus compressed compared with the case in which the position information is directly encoded.
An initial position information encoding unit 2702 encodes initial position information using an ordinary method rather than a difference technique. As shown in FIG. 28, initial position information (0,0) is represented by 10 bits=5 bits×2 with 5 bits per variable. At the same time, the initial position information (0,0) is input to and stored in a preceding position information storage unit 2703 to be used for encoding next position information (0,1).
A branch layer determining unit 2704 compares input position information being encoded next with the position information stored in the preceding position information storage unit 2703, determines a branch layer based on the comparison results, and outputs the determination results to a differential position information encoding unit 2705. As shown in FIG. 28, second position information (0,1) being encoded next and the position information (0,0) stored in the preceding position information storage unit 2703 has the identical value of the first layer, namely, the scene layer. The value of the position information of the second layer, namely, the shot layer is increased. This means that the paths branch off at the second layer=shot layer. The determination results are output to the differential position information encoding unit 2705.
The differential position information encoding unit 2705 selects and outputs a position information code according to the determination results of the branch layer determining unit 2704. Since the branch layer determining unit 2704 determines that the branch layer between (0,1) and (0,0) is the second layer, a code “10” indicating that the branch layer is the second layer (a position information code indicating an increment of 1 to the second layer) is provided as shown in FIG. 28. Similarly, a code “10” indicating the second layer is provided to third position information (0,2). If the branch layer determining unit 2704 compares fourth position information (1,0) with the third position information (0,2), it is learned that the value of the position information of the first layer, namely, the scene layer has increased. The branching takes place at the first layer=the scene layer. Therefore, a code “01” (a position information code indicating an increment of 1 to the first layer) is provided to indicate that the branch layer is the first layer. The position information code string obtained by encoding to the end is the one shown in FIG. 28. The position information code string has nothing at the end, more specifically, ends with an end code “11” indicating the end of the code.
FIG. 29 illustrates the position information code corresponding to the branch layer of FIG. 28.
FIG. 30 is a functional block diagram illustrating the schematic structure of a decoding device for position information by differential encoding of the known technique.
First, an initial position information decoding unit 3001 decodes initial position information using an ordinary decoding method. The decoded position information is input to and stored in a preceding position storage unit 3002. A branch layer determining unit 3003 reads a position information code. The branch layer determining unit 3003 determines a branch layer based on the read position information code, and sends the determination results to a differential position information decoding unit 3004. Upon receiving the determination results, the differential position information decoding unit 3004 updates the value of position information stored in the preceding position information storage unit 3002, and outputs the updated position information. The updated position information is stored in the preceding position information storage unit 3002. That process is repeated until the end code is read.
The branch layer determining unit 3003 reads a code “10” with the decoded initial position information (0,0) stored in the preceding position information storage unit 3002. Since the code “10” indicates the branching at the second layer, the differential position information decoding unit 3004 increases the value (0,0) of the second layer by 1, thereby resulting in next position information (0,1). Then, the branch layer determining unit 3003 reads a code “01” with (0,2) decoded and stored in the preceding position information storage unit 3002. Since the code “01” indicates the branching at the first layer, the differential position information decoding unit 3004 increases the position information (0,2) of the first layer which is stored in the preceding position information storage unit 3002 by 1. Since the value of the first layer has changed, position information at a layer below is set to the initial value 0. Next position information (1,0) is thus obtained. That process is performed to the end and decoding is completed when an end code “11” is read.
In these latter days, the above-referenced position information is typically represented by rational numbers. For example, as shown in FIG. 2, all position information is represented by a rational number greater than 0 but smaller than 1, such as a natural number over power of 2 (the denominator being power of 2 and the numerator being a natural number). Such a notation is introduced to make it possible to add a leaf or node optionally between existing leaves or nodes.
For example, as shown in FIG. 26, another shot cannot be added between shot #0 and shot #1 under scene #0 in the current state. To add another shot, the shot number below shot #1 needs to be re-numbered. On the other hand, the position information is represented in a rational number as shown in FIG. 2. If a new shot is added between shot #(1/4) and shot #(1/2) below scene #(1/4), the new shot may be assigned position information 3/8. The new shot is thus added without modifying the existing shots.